package com.tuling.code;

/**
 * 最小和问题与逆序对问题
 *
 * 最小和问题是考： 右边右多少个数比当前位置数大
 * 逆序对问题考：  当前位置数有多少个数比当前位置数小
 *
 */
public class MergeMinSum {
    public static void main(String[] args) {

    }

  public int process(int[] arry,int left,int right){
        if(left == right){return arry[left];}

        int mid  = left + ((right - left)>>1);

        return process(arry,left,mid) +
        process(arry,mid+1,right)+
        merge(arry,left,mid,right);
  }

    private int merge(int[] arry, int left, int mid, int right) {
        int[] help  = new int[right - left +1];
        int i = 0;
        int p1 = left;
        int p2 = mid +1;
        int res = 0;
        while (p1 <=mid && p2 <= right){
            //计算最小和  左组小于右组 产生小和 当左组和右组相等 拷贝右组
            res += arry[p1] < arry[p2] ? arry[p1] * (right -p2 +1) :0;
            help[i++] = arry[p1] < arry[p2] ? arry[p1++] : arry[p2++];
        }

        while (p1 <= mid){
            help[i++] = arry[p1++];
        }

        while (p2 <= right){
            help[i++] = arry[p2++];
        }

        return res;
    }
}
